package Sort;

import java.util.Arrays;

//堆排序
//升序要建立大根堆
public class HeadSort {
    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6,0};
        headSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    //1.创建大根堆
    public static void createBigHead(int[] arr){
        for(int parent = (arr.length-2)/2;parent>=0;parent--){
            int len = arr.length;
            shiftDown(parent,arr,len);
        }
    }
    //2.向下调整
    public static void shiftDown(int parent,int[] arr,int len){
        //int len = arr.length;
        int child = 2*parent+1;
        if(child+1<len && arr[child] < arr[child+1]){
            //找到最大的孩子
            child = child+1;
        }
        //一定要判断好边界
        while(child < len){
//            if(child+1<len && arr[child] < arr[child+1]){
//                //找到最大的孩子
//                child = child+1;
//            }
            if(arr[parent] < arr[child]){
                swap(arr,parent,child);
                parent = child;
                child = parent*2+1;
            }else{
                break;
            }
        }

    }
    //3.进行堆排序
    public static void headSort(int[] arr){
        createBigHead(arr);
        int end = arr.length -1;
        while(end > 0){
            swap(arr,0,end);
            //end--;
            shiftDown(0,arr,end);
            end--;
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
